class Trie{
public:
    unordered_map<char,Trie*> next;
    bool isEnd = false;
    Trie(){}
                                        
    void insert(string word){
        Trie* cur = this;
        for(char c : word){
            if(!cur->next.count(c)){
                cur->next[c] = new Trie();
            }
            cur = cur->next[c];
        }
        cur->isEnd = true;
    }
                                        
    bool dfs(Trie* root,int pos,bool flag,string& s){
        if(pos == s.size()){
            return flag && root->isEnd;
        }
        if(root->next.count(s[pos])){
            if(dfs(root->next[s[pos]],pos+1,flag,s)){
                return true;
            }
        }
        if(!flag){
            for(auto& [k,T] : root->next){
                if(k != s[pos]){
                    if(dfs(T,pos+1,true,s)){
                        return true;
                    }
                }
            }
        }
        return false;
    }
};
class MagicDictionary {
public:
    /** Initialize your data structure here. */
    Trie* root;
    MagicDictionary() {
        root = new Trie();
    }
    
    void buildDict(vector<string> dictionary) {
        for(auto& s : dictionary){
            root->insert(s);
        }
    }
    
    bool search(string searchWord) {
        return root->dfs(root,0,false,searchWord);
    }   
};
